#define MAXN 100010
#define MAXM 2000010

struct graph
{
	int a[MAXN],b[MAXM],c[MAXM],d[MAXM];
	int dist[MAXN];
	set<ipair> C;
	void clear()
	{
		memset(a,0,sizeof a);
		p=1;
	}
	void addedge(int x,int y,int z,int w)
	{
		c[++p]=a[x]; a[x]=p; b[p]=y; d[p]=z;
		c[++p]=a[y]; a[y]=p; b[p]=x; d[p]=z;
	}
	void mindist(int S)
	{
		C.clear();
		for(int i=1;i<=n;i++) dist[i]=1000000000;
		dist[S]=0;
		for(int i=1;i<=n;i++) C.insert(mp(dist[i],i));
		while(!C.empty())
		{
			int now=C.begin()->se;
			C.erase(C.begin());
			for(int i=a[now];i;i=c[i]) if (dist[b[i]]>dist[now]+d[i])
			{
				C.erase(mp(dist[b[i]],b[i]));
				dist[b[i]]=dist[now]+d[i];
				C.insert(mp(dist[b[i]],b[i]));
			}
		}
	}
};